package org.lql.algo.codecrush.week010;

import org.lql.algo.common.Pair;
import org.lql.algo.common.TreeNode;

/**
 * @author: liangqinglong
 * @date: 2025-08-26 15:13
 * @description: 236. 二叉树的最近公共祖先 <a href="https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/">...</a>
 **/
public class LowestCommonAncestor {

	TreeNode p;
	TreeNode q;
	TreeNode ans;

	public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
		this.p = p;
		this.q = q;
		dfs(root);
		return ans;
	}

	public Pair<Boolean, Boolean> dfs(TreeNode root) {
		// 边界判断：为空，就不再是公共祖先
		if (root == null) {
			return new Pair<>(false, false);
		}
		Pair<Boolean, Boolean> left = dfs(root.left);
		Pair<Boolean, Boolean> right = dfs(root.right);
		boolean key = left.getKey() || right.getKey() || root.val == p.val;
		boolean value = left.getValue() || right.getValue() || root.val == q.val;
		if (key && value && ans == null) {
			ans = root;
		}
		return new Pair<>(key, value);
	}
}
